#include <bits/stdc++.h>
// 2025/05/17
// tag: Persistent Union Find
// Author: Forever
using namespace std;
using int64 = int64_t;

#define MAXN 1000001

class PA {
private:
    int size, type, idx, rt[MAXN];
    struct Segmenttree {
        int lc, rc, val;
    } tr[MAXN * 32];
    int build(int s, int t)
    {
        int x = ++idx;
        tr[x].val = 0;
        if (s == t) {
            tr[x].val = (type ? s : 1);
            return x;
        }
        int mid = (s + t) >> 1;
        tr[x].lc = build(s, mid), tr[x].rc = build(mid + 1, t);
        return x;
    }
    int update(int cur, int l, int r, int x, int s)
    {
        int k = ++idx;
        tr[k] = tr[cur];
        if (l == r) {
            tr[k].val = s;
            return k;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            tr[k].lc = update(tr[k].lc, l, mid, x, s);
        else
            tr[k].rc = update(tr[k].rc, mid + 1, r, x, s);
        return k;
    }
    int& query(int cur, int l, int r, int k)
    {
        if (l == r)
            return tr[cur].val;
        int mid = (l + r) >> 1;
        if (k <= mid)
            return query(tr[cur].lc, l, mid, k);
        else
            return query(tr[cur].rc, mid + 1, r, k);
    }

public:
    int cnt;
    PA(int n, int t)
    {
        idx = 0;
        size = n;
        type = t;
        rt[0] = build(1, n);
        cnt = 0;
    }
    void update(int l, int x, int s)
    {
        rt[++cnt] = update(rt[l], 1, size, x, s);
    }
    int& operator()(int l, int k)
    {
        return query(rt[l], 1, size, k);
    }
};

class PUF {
private:
    PA p, s; // p存储父节点，s存储秩/深度
    int size, cnt, rt[MAXN];

public:
    PUF(int n)
        : p(n, 1)
        , size(n)
        , s(n, 0)
        , cnt(0)
    {
        rt[0] = p.cnt;
    }

    // 查找根节点，需要指定版本
    int find(int ver, int a)
    {
        int fa = p(rt[ver], a);
        if (fa == a)
            return a;
        return find(ver, fa); // 递归查找根节点
    }

    // 合并两个集合，指定当前版本和上一版本
    void merge(int a, int b, int now)
    {
        int fx = find(now - 1, a), fy = find(now - 1, b);
        if (fx == fy) {
            rt[now] = rt[now - 1]; // 如果已在同一集合，直接复制前一版本
            return;
        }

        // 按秩合并
        if (s(rt[now - 1], fx) >= s(rt[now - 1], fy)) {
            s.update(rt[now - 1], fx, s(rt[now - 1], fx) + 1); // 更新fx的秩
            p.update(rt[now - 1], fy, fx); // 更新fy的父节点为fx
            rt[now] = p.cnt; // 更新当前版本
        } else {
            s.update(rt[now - 1], fy, s(rt[now - 1], fy) + 1); // 更新fy的秩
            p.update(rt[now - 1], fx, fy); // 更新fx的父节点为fy
            rt[now] = p.cnt; // 更新当前版本
        }
    }

    // 回滚到指定版本
    void rollback(int k, int now)
    {
        rt[now] = rt[k];
    }

    // 检查两个元素是否在同一集合
    bool same(int ver, int a, int b)
    {
        return find(ver, a) == find(ver, b);
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    PUF p(n);
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        cin >> opt;
        if (opt == 1) {
            cin >> x >> y;
            p.merge(x, y, i); 
        } else if (opt == 2) {
            cin >> x;
            p.rollback(x, i); 
        } else {
            cin >> x >> y;
            if (p.same(i - 1, x, y)) 
                cout << 1 << endl;
            else
                cout << 0 << endl;
            p.rollback(i - 1, i); 
        }
    }
    return 0;
}